\subsection{Gaussian integers}
Recall the ring of Gaussian integers \( \mathbb Z[i] = \qty{a+bi \colon a, b \in \mathbb Z} \leq \mathbb C \).
There is a norm function \( N \colon \mathbb Z[i] \to \mathbb Z_{\geq 0} \) given by \( a + bi \mapsto a^2 + b^2 \), and \( N(xy) = N(x) N(y) \).
This norm is a Euclidean function, giving the Gaussian integers the structure of a Euclidean domain and hence a principal ideal domain and a unique factorisation domain.
In particular, the primes are the irreducibles.
The units in \( \mathbb Z[i] \) are \( \pm 1, \pm i \), since they are the only elements of unit norm.
\begin{example}
	2 is not irreducible in \( \mathbb Z[i] \), since it factors as \( (1+i)(1-i) \).
	5 is not irreducible, since it factors as \( (2+i)(2-i) \).
	These are nontrivial factorisations since the norms of the factors are not unit length.

	3 is a prime, since it is irreducible.
	Indeed, \( N(3) = 9 \), so if 3 were reducible it would factor as \( ab \) where \( N(a) = N(b) = 3 \).
	But \( \mathbb Z[i] \) has no elements of norm 3.
	Similarly, 7 is a prime.
\end{example}
\begin{proposition}
	Let \( p \in \mathbb Z \) be a prime.
	Then, the following are equivalent.
	\begin{enumerate}
		\item \( p \) is not prime in \( \mathbb Z[i] \);
		\item \( p = a^2 + b^2 \) for \( a, b \in \mathbb Z \);
		\item \( p = 2 \) or \( p \equiv 1 \text{ mod } 4 \).
	\end{enumerate}
\end{proposition}
\begin{proof}
	Suppose \( p \) is not prime in \( \mathbb Z[i] \).
	So let \( p = xy \) for \( x, y \in \mathbb Z[i] \) not units.
	Then, \( p^2 = N(p) = N(x)N(y) \).
	Since \( x, y \) are not units, \( N(x), N(y) > 1 \) and in particular \( N(x) = N(y) = p \).
	Writing \( x = a+bi \) for \( a, b \in \mathbb Z \), we have \( p = N(x) = a^2 + b^2 \), which is the condition in (ii).

	Now, suppose \( p = a^2 + b^2 \).
	The only squares modulo 4 are 0 and 1.
	Since \( p \equiv a^2 + b^2 \text{ mod } 4 \), we have that \( p \) cannot be congruent to 3, modulo 4.

	Finally, suppose \( p = 2 \) or \( p \equiv 1 \text{ mod } 4 \).
	We have already observed above that 2 is not prime.
	It hence suffices to consider the case where \( p \equiv 1 \text{ mod } 4 \).
	We have that \( \qty(\faktor{\mathbb Z}{p\mathbb Z})^\times \) is cyclic of order \( p-1 \) by a previous theorem.
	Hence, if \( p \equiv 1 \text{ mod } 4 \), we have that \( 4 \mid p-1 \), and hence \( \qty(\faktor{\mathbb Z}{p\mathbb Z})^\times \) contains an element of order 4.
	In particular, there exists \( x \in \mathbb Z \) with \( x^4 \equiv 1 \text{ mod } p \), but \( x^2 \not\equiv 1 \text{ mod } p \).
	Then \( x^2 \equiv -1 \text{ mod } p \), or in other words, \( p \mid (x^2 + 1) \).
	But this factorises as \( p \mid (x+i)(x-i) \).
	We can see that \( p \nmid x+i \), \( p \nmid x-i \), so \( p \) cannot be prime.
\end{proof}
\begin{remark}
	The proof that (iii) implies (ii) is entirely nontrivial.
	It required lots of theory in order to reach the result, even though its statement did not require even the notion of a complex number.
\end{remark}
\begin{theorem}
	The primes in \( \mathbb Z[i] \) are, up to associates,
	\begin{enumerate}
		\item \( a + bi \), where \( a, b \in \mathbb Z \) and \( a^2 + b^2 = p \) is a prime in \( \mathbb Z \) with \( p = 2 \) or \( p \equiv 1 \text{ mod } 4 \); and
		\item the primes \( p \) in \( \mathbb Z \) satisfying \( p \equiv 3 \text{ mod } 4 \).
	\end{enumerate}
\end{theorem}
\begin{proof}
	First, we must check that all such elements are prime.
	For (i), note that \( N(a+bi) = p \) is prime, so \( a+bi \) is irreducible.
	We can use the above proof to deduce that primes in \( \mathbb Z \) of form (ii) are primes in \( \mathbb Z[i] \).

	It now suffices to show that any prime in the Gaussian integers satisfies one of the two above conditions.
	Let \( z \) be prime in \( \mathbb Z[i] \).
	We note that \( \overline z \) is also irreducible.
	Now, \( N(z) = z\overline z \), which is a factorisation of the norm into irreducibles.

	Let \( p \) be a prime in \( \mathbb Z \) dividing \( N(z) \).
	If \( p \equiv 3 \text{ mod } 4 \), \( p \) is prime in \( \mathbb Z[i] \).
	So \( p \mid z \) or \( p \mid \overline z \) so \( p \) is associate to \( z \) or \( \overline z \).

	Otherwise, \( p = a^2 + b^2 = (a+bi)(a-bi) \) where \( a \pm bi \) are prime in \( \mathbb Z[i] \) as they have norm \( p \).
	So we have \( p = (a+bi)(a-bi) \mid z \overline z \), so \( z \) is an associate of \( a+bi \) or \( a-bi \) by uniqueness of factorisation.
\end{proof}
\begin{remark}
	In the above theorem, if \( p = a^2 + b^2 \), \( a+bi \) and \( a-bi \) are not associate unless \( p = 2 \).
\end{remark}
\begin{corollary}
	An integer \( n \geq 1 \) is the sum of two squares if and only if every prime factor \( p \) of \( n \) with \( p \equiv 3 \text{ mod } 4 \) divides \( n \) to an even power.
\end{corollary}
\begin{proof}
	Suppose \( n = a^2 + b^2 \).
	So \( n = N(a+bi) \).
	Hence \( n \) is a product of norms of primes in the Gaussian integers.
	By the classification above, those norms are
	\begin{enumerate}
		\item the primes \( p \in \mathbb Z \) with \( p \not\equiv 3 \text{ mod } 4 \); and
		\item squares of primes \( p \in \mathbb Z \) with \( p \equiv 3 \text{ mod } 4 \).
	\end{enumerate}
	The result follows.
\end{proof}
\begin{example}
	We can write \( 65 = 5 \cdot 13 \) as the sum of two primes since \( 5, 13 \equiv 1 \text{ mod } 4 \).
	We first factorise 5 and 13 into primes in the Gaussian integers.
	\[
		5 = (2+i)(2-i);\quad 13 = (2+3i)(2-3i)
	\]
	Thus, the factorisation of 65 into irreducibles in \( \mathbb Z[i] \) is
	\begin{align*}
		65 & = (2+3i)(2+i)(2-3i)(2-i)                \\
		   & = [(2+3i)(2+i)]\overline{[(2+3i)(2+i)]} \\
		   & = N((2+3i)(2-i))                        \\
		   & = N(1+8i) = 1^2 + 8^2
	\end{align*}
	This was dependent on the choice of grouping of terms.
	Alternatively,
	\[
		65 = N((2+i)(2-3i)) = N(7+4i) = 7^2 + 4^2
	\]
\end{example}

\subsection{Algebraic integers}
\begin{definition}
	A number \( \alpha \in \mathbb C \) is \textit{algebraic} if \( \alpha \) is a root of some nonzero polynomial \( f \in \mathbb Q[X] \).
	\( \alpha \) is an \textit{algebraic integer} if it is a root of some monic polynomial \( f \in \mathbb Z[X] \).
\end{definition}
Let \( R \leq S \), and \( \alpha \in S \).
We write \( R[\alpha] \) to denote the smallest subring of \( S \) containing \( R \) and \( \alpha \).
Alternatively, \( R[\alpha] \) is the intersection of all subrings of \( S \) containing \( R \) and \( \alpha \).
Further, \( R[\alpha] = \Im \varphi \) where \( \varphi \colon R[X] \to S \) is the homomorphism \( g(X) \mapsto g(\alpha) \).
\begin{definition}
	Let \( \alpha \) be an algebraic number.
	Consider the homomorphism \( \varphi \colon \mathbb Q[X] \to \mathbb C \) where \( g(X) \mapsto g(\alpha) \).
	Since \( \mathbb Q[X] \) is a a principal ideal domain, \( \ker \varphi = (f) \) for some \( f \in \mathbb Q[X] \).
	This ideal contains a nonzero element since \( \alpha \) is an algebraic number, hence \( f \) is nonzero.
	Multiplying \( f \) by a unit, we may assume \( f \) is monic without loss of generality.
	This unique \( f \) is known as the \textit{minimal polynomial} of \( \alpha \).
\end{definition}
\begin{corollary}
	All minimal polynomials are irreducible.
	By the first isomorphism theorem, \( \faktor{\mathbb Q[X]}{(f)} \cong \mathbb Q[\alpha] \leq \mathbb C \).
	Any subring of a field is an integral domain.
	Hence \( (f) \) is a prime ideal in \( \mathbb Q[X] \), and hence \( f \) is irreducible.
	In particular, this implies that \( \mathbb Q[\alpha] \) is a field.
\end{corollary}
\begin{proposition}
	Let \( \alpha \) be an algebraic integer, and \( f \in \mathbb Q[X] \) be its minimal polynomial.
	Then \( f \in \mathbb Z[X] \), and \( (f) = \ker \theta \vartriangleleft \mathbb Z[X] \) where \( \theta \colon \mathbb Z[X] \to \mathbb C \) is given by \( g(X) \mapsto g(\alpha) \).
\end{proposition}
\begin{remark}
	If \( \alpha \) is an algebraic integer, then the polynomial in the definition can be taken to be minimal without loss of generality.
	\( \mathbb Z[X] \) is not a principal ideal domain, so the above argument cannot work verbatim.
\end{remark}
\begin{proof}
	Let \( f \) be the minimal polynomial of \( \alpha \).
	Let \( \lambda \in \mathbb Q^\times \) such that \( \lambda f \) has coefficients in \( \mathbb Z \) and is primitive.
	Then \( \lambda f(\alpha) = 0 \), so \( \lambda f \in \ker \theta \).

	Let \( g \in \ker \theta \), so in particular \( g \in \mathbb Z[X] \).
	Then \( g \in \ker \varphi \), and hence \( \lambda f \mid g \) in \( \mathbb Q[X] \).
	By a previous lemma, \( \lambda f \mid g \) in \( \mathbb Z[X] \).
	Thus, \( \ker \theta = (\lambda f) \).

	Now, since \( \alpha \) is an algebraic integer, we know that there exists a monic polynomial \( g \in \ker \theta \) such that \( g(\alpha) = 0 \).
	Then \( \lambda f \mid g \) in \( \mathbb Z[X] \), so \( \lambda = \pm 1 \) as both \( f, g \) are monic.
	Hence, \( f \in \mathbb Z[X] \), and \( (\lambda f) = (f) = \ker \theta \).
\end{proof}
Let \( \alpha \in \mathbb C \) be an algebraic integer.
Then, applying the isomorphism theorem to \( \theta \), \( \faktor{\mathbb Z[X]}{(f)} \cong \mathbb Z[\alpha] \).
For example:
\begin{align*}
	\faktor{\mathbb Z[X]}{(X^2 + 1)}     & \cong \mathbb Z[i]                          \\
	\faktor{\mathbb Z[X]}{(X^2 - 2)}     & \cong \mathbb Z\qty[\sqrt{2}]               \\
	\faktor{\mathbb Z[X]}{(X^2 + X + 1)} & \cong \mathbb Z\qty[\frac{-1+\sqrt{-3}}{2}] \\
	\faktor{\mathbb Z[X]}{(X^n - p)}     & \cong \mathbb Z\qty[\sqrt[n]{p}]
\end{align*}
\begin{corollary}
	If \( \alpha \) is an algebraic integer, and \( \alpha \in \mathbb Q \), then \( \alpha \in \mathbb Z \).
\end{corollary}
\begin{proof}
	Let \( \alpha \neq 0 \), since the case where \( \alpha = 0 \) is trivial.
	Then the minimal polynomial of \( \alpha \) has coefficients in \( \mathbb Z \).
	Since \( \alpha \) is rational, the minimal polynomial is \( X - \alpha \).
	Hence \( \alpha \in \mathbb Z \) as it is a coefficient of the minimal polynomial.
\end{proof}
